package nowCoder;

import java.util.ArrayList;
import java.util.Stack;

/**
 * 
 * @author Ghost
 *
 */
public class IsPopOrder {
    public boolean IsPopOrder(ArrayList<Integer> pushA,ArrayList<Integer> popA) {
    	if(pushA==null || popA==null || pushA.size()!=popA.size())//边界
    		return false;
    	if(pushA.size()==0 && popA.size()==0)//边界
    		return true;
    	Stack<Integer> stack = new Stack<Integer>();
    	Integer first = popA.get(0);
    	Integer[] pushArray  = new Integer[pushA.size()];
    	pushA.toArray(pushArray);
    	int i;
    	for(i=0;i<pushArray.length && pushArray[i]!= first;i++){
    		stack.push(pushArray[i]);
    	}
    	if(i<pushArray.length)
    		stack.push(pushArray[i]);
    	else {
			return false;
		}
    	int begin = i+1;
    	for(Integer I:popA){
    		if(stack.peek()==I){
    			stack.pop();
    		} else{
    			for(;begin<pushArray.length && pushArray[begin]!=I;begin++){//注意该处逻辑
    				stack.push(pushArray[begin]);
    			}
    			if(begin==pushArray.length)
    				return false;
    			else{
    				stack.push(pushArray[begin]);
    				begin++;
    				stack.pop();
    			}
    		}
    	}
    	return true;
    }
    
    public static void main(String[] args){
    	IsPopOrder isPopOrder = new IsPopOrder();
    	ArrayList<Integer> pushA = new ArrayList<Integer>();
    	ArrayList<Integer> popA = new ArrayList<Integer>();
    	
    	pushA.add(1);
//    	pushA.add(2);
//    	pushA.add(3);
//    	pushA.add(4);
//    	pushA.add(5);

//    	popA.add(3);
//    	popA.add(5);
//    	popA.add(4);
//    	popA.add(1);
    	popA.add(2);
    	System.out.println(isPopOrder.IsPopOrder(pushA, popA));
    }
}
